package 剑指offer;

import common.TreeNode;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

/**
 * @author zhangmin
 * @create 2021-12-08 11:11
 */
public class day28_37_38 {

    /**==============================================================================================================================================
     * 剑指 Offer 37. 序列化二叉树
     * 请实现两个函数，分别用来序列化和反序列化二叉树。你需要设计一个算法来实现二叉树的序列化与反序列化。
     * 这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构
     * 1、前序遍历
     * 2、后序遍历
     * 3、层序遍历
     * */
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuffer sb=new StringBuffer();
        serializePre(root,sb);
        return sb.toString();
    }
    void serializePre(TreeNode root,StringBuffer sb){
        if (root==null){
            sb.append("#").append(",");
            return;
        }
        sb.append(root.val).append(",");
        serializePre(root.left,sb);
        serializePre(root.right,sb);
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] strings = data.split(",");
        LinkedList<String> nodes=new LinkedList<>();
        for (String s:strings) {
            nodes.add(s);
        }
        return deserializePre(nodes);
    }
    TreeNode deserializePre(LinkedList<String> nodes){
        if (nodes.isEmpty()) return null;
        String first = nodes.removeFirst();
        if (first.equals("#")) return null;
        TreeNode root=new TreeNode(Integer.parseInt(first));
        root.left=deserializePre(nodes);
        root.right=deserializePre(nodes);
        return root;
    }


    /**==============================================================================================================================================
     * 剑指 Offer 38. 字符串的排列
     * 输入一个字符串，打印出该字符串中字符的所有排列。1 <= s 的长度 <= 8
     * 回溯：
     * 选择列表：s中没有用过的字符
     * 路径：按顺序选择好的字符序列
     * 终止条件：s中的全部字符被访问过
     * */
    Set<String> set=new HashSet<>();
    boolean[] visited=new boolean[9];
    void backtrack(char[] cs,int index,String path){
        int n=cs.length;
        if (index==n){
            set.add(path);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!visited[i]){
                //做出选择
                visited[i]=true;
                backtrack(cs,index+1,path+String.valueOf(cs[i]));
                //取消选择
                visited[i]=false;
            }
        }
    }

    public String[] permutation(String s) {
        char[] cs = s.toCharArray();
        backtrack(cs,0,"");
        String[] res=new String[set.size()];
        int i=0;
        for (String str:set) {
            res[i++]=str;
        }
        return res;
    }
}
